package com.wj.algorithm.lintcode;

public class P163 {
    
    static int[] arr = null;
    public int numTrees1(int n) {
        if(n <= 1) {
            return 1;
        }

        int total = 0;
        int start = 0;
        int end = n - 1;
        while(start <= n - 1 && end >= 0) {
            if(start == end) {
                int temp = arr[start];
                if(temp <= 0) {
                    temp = numTrees1(start);
                    arr[start] = temp;
                } 
                total += temp * temp;
            } else {

                int temp1 = arr[start];
                if(temp1 <= 0) {
                    temp1 = numTrees1(start);
                    arr[start] = temp1;
                } 
                int temp2 = arr[end];
                if(temp2 <= 0) {
                    temp2 = numTrees1(end);
                    arr[end] = temp2;
                } 
                total += temp1 * temp2;
            }
            start ++;
            end --;
        }
        return total;
    }
    
    public int numTrees(int n) {
        if(n <= 1) {
            return 1;
        }
        arr = new int[n];

        return numTrees1(n);
    }
    
    public static void main(String[] args) {
        
        System.out.println(new P163().numTrees(19));
    }
}
